package heap;
import java.util.Arrays;

public class BigHeap {
    //模拟实现大根堆
    /**
     * 堆的底层是由完全二叉树实现的，大根堆就是一种特殊的完全二叉树*/
    public int[] elem;
    public int usedSize;
    private static final int DEFAULT_CAPACITY = 10;
    public BigHeap() {
        this.elem = new int[DEFAULT_CAPACITY];
    }
    public BigHeap(int capacity) {
        if (capacity<=0) {
            //抛异常
        }
        this.elem = new int[capacity];
    }

    /**
     * 通过数组进行赋值*/
    public void initHeap(int[] array) {
        for(int i = 0; i < array.length; i++) {
            this.elem[i] = array[i];
            this.usedSize++;
        }
    }

    /**
     * 使用向下调整的方式创建大根堆
     * 从最后一棵树开始调整*/
    public void createHeap() {
        int parent = (usedSize-1-1)/2;//最后一个节点下标-1 再除以2
        for(int i = parent; i >= 0; i--) {
            siftDown(i,usedSize);
        }
    }

    /**
     * 交换两个元素*/
    private void swap(int e1, int e2) {
        int tmp = elem[e1];
        elem[e1] = elem[e2];
        elem[e2] = tmp;
    }

    /**
     * 出堆 返回出堆的数
     * 直接让0下标元素和最后一个元素互换
     * usdSize--
     * 向下调整0下标位置即可*/
    public int pop() {
        if(isEmpty()) {
            //抛异常
            return -1;
        }
        int ret = this.elem[0];
        swap(0,this.usedSize-1);
        this.usedSize--;
        siftDown(0,this.usedSize);
        return ret;
    }

    /**
     * 入堆
     * 先判满 若是满则扩容
     * 将新的元素放置在usedSize下标处
     * usedSize++
     * 向上调整*/
    public void push(int val) {
        if(isFull()) {
            this.elem = Arrays.copyOf(this.elem,this.usedSize*2);
        }
        this.elem[this.usedSize] = val;
        this.usedSize++;
        siftUp(this.usedSize-1);
    }

    /**
     * 堆排序-从小到大排序使用大根堆
     * 将0下标的值与end下标值交换
     * 向下调整0下标
     * end--*/
    public void heapSort() {
        int end = this.usedSize-1;
        while(end>0) {
            swap(0,end);
            //当0和end交换之后，end下标就不参与向下调整，故向下调整直接传递end
            siftDown(0,end);
            end--;
        }
    }

    /**
     * 向下调整
     * 子节点下标求法：父节点下标*2 + 1*/
    private void siftDown(int parent,int len) {
        int child = parent*2+1;
        while(child<len) {
            //能进循环，说明至少存在左孩子
            if(child+1<len && elem[child]<elem[child+1]) {
                child+=1;
            }
            //走到此处，说明child为左右孩子中值最大的孩子的下标
            if(elem[child]>elem[parent]) {
                swap(child,parent);
                parent = child;
                child = 2*child+1;
            } else {
                break;
            }
        }
    }

    /**
     * 向上调整
     * 父节点下标求法：父节点下标 == （子节点下标-1）/2
     * */
    private void siftUp(int child) {
        int parent = (child-1)/2;
        while(child>0) {
            if(this.elem[child]>this.elem[parent]) {
                swap(child,parent);
                child = parent;
                parent = (child-1)/2;
            } else {
                break;
            }
        }
    }

    /**
     * 判空
     * 如果元素个数为零，则堆为空*/
    private boolean isEmpty() {
        return this.usedSize==0;
    }

    /**
     * 判满
     * 如果元素个数==数组长度，说明堆已满*/
    private boolean isFull() {
        return this.usedSize == this.elem.length;
    }
}
